package com.dylan.algorithm.subList;

import cn.hutool.json.JSONUtil;
import com.google.common.collect.Lists;
import org.apache.commons.collections4.CollectionUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhangshaojian
 * @description
 * @date 2022/3/31 9:51
 */
public class SubListTest {
    public static void main(String[] args) {
        List<Integer> integers = Lists.newArrayList(1, 4, 9);
        List<List<Integer>> lists = subList(integers);
        System.out.println(JSONUtil.toJsonStr(lists));
        System.out.println("=============================");
        List<List<Integer>> subList = binarySubList(integers);
        System.out.println(JSONUtil.toJsonStr(subList));

    }

    /**
     * 地柜算法
     */
    public static List<List<Integer>> subList(List<Integer> lists) {
        if (CollectionUtils.isEmpty(lists)) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(Collections.emptyList());
            return result;
        }
        Integer first = lists.get(0);
        List<Integer> sub = lists.subList(1, lists.size());
        System.out.println("first:" + first + "====sub:" + JSONUtil.toJsonStr(sub));
        List<List<Integer>> subSub = subList(sub);
        System.out.println("first:" + first + "subSub" + JSONUtil.toJsonStr(subSub));
        List<List<Integer>> result = insertAll(first, subSub);
        System.out.println("result" + JSONUtil.toJsonStr(result));
        concat(subSub, result);
        return subSub;
    }

    private static void concat(List<List<Integer>> subSub, List<List<Integer>> result) {
        subSub.addAll(result);
    }

    private static List<List<Integer>> insertAll(Integer first, List<List<Integer>> subSub) {
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> integers : subSub) {
            List<Integer> temp = new ArrayList<>();
            temp.add(first);
            temp.addAll(integers);
            result.add(temp);
        }
        return result;
    }

    // 根据集合包含的元素存在与否计算可知1,4,9一共有2x2x2种排列，每个数字存在与否对应二进制的数字.
    // 000,001,010,100,011,101,110,111 根据对应数字映射原集合中的数字。
    // =====================================================================================

    private static List<List<Integer>> binarySubList(List<Integer> container) {
        Map<Integer, Integer> map = turnToMap(container);
        int count = 2 << container.size() - 1;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            String binaryStr = Integer.toBinaryString(i);
            List<Integer> integers = binaryToList(binaryStr, map);
            result.add(integers);
        }
        return result;
    }

    private static List<Integer> binaryToList(String binaryStr, Map<Integer, Integer> map) {
        List<Integer> result = new ArrayList<>();
        char[] chars = binaryStr.toCharArray();
        int count = -1;
        for (int i = chars.length - 1; i >= 0; i--) {
            ++count;
            char aChar = chars[i];
            if (aChar != '0') {
                Integer integer = map.get(2 << count);
                result.add(integer);
            }
        }
        System.out.println(JSONUtil.toJsonStr(result));
        return result;
    }

    private static Map<Integer, Integer> turnToMap(List<Integer> container) {
        Map<Integer, Integer> result = new HashMap<>(container.size());
        int count = -1;
        for (int size = container.size() - 1; size >= 0; size--) {
            result.put(2 << ++count, container.get(size));
        }
        return result;
    }

}
